Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут прикладної математики
і фундаментальних наук
Кафедра прикладної математики
Лабораторна робота № 2
Знаходження шляхів графа
Виконав: студент групи ПМ-22
Львів 2007
Умова задачі:
5.6. Знайти найкоротший шлях від вершини Хi і Хj ( i і j – дві останні цифри номера залікової книжки) графа заданого Х описом:
(1,4; 1,5; 2,13; 2,14; 3,21; 3,25; 4,10; 4,11; 4,12; 5,12; 5,19; 5,20; 6,4; 6,5; 7,13; 7,14; 8,16; 8,18; 18,9; 10,14; 11,16; 11,22; 11,17; 11,18; 12,6; 12,9; 9,13; 15,25; 16,22; 23,17; 15,17; 17,21; 18,23; 18,24; 19,11; 19,17; 19,24; 20,24; 20,21; 20,9; 0,1; 0,11; 0,13; 0,20)
Текст програми:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
//-----------------------------CONSTANTS
const int kilver = 26; //kilkist vershyn
const int q = 2*kilver; //mnogyny Lm
//-----------------------------VARIABLES
matrycya_sumignosti[kilver][kilver]= {
// 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
/*0*/{0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0},
/*1*/{1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*2*/{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0},
/*3*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1},
/*4*/{0,1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*5*/{0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0},
/*6*/{0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*7*/{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0},
/*8*/{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0},
/*9*/{0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0},
/*0*/{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
/*1*/{1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0},
/*2*/{0,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*3*/{1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*4*/{0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*5*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
/*6*/{0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
/*7*/{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0},
/*8*/{0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0},
/*9*/{0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0},
/*0*/{1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0},
/*1*/{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0},
/*2*/{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
/*3*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0},
/*4*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0},
/*5*/{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}};
int mnogyna[q][kilver];
int nevybrani[kilver];
int k; //kilkilst dodanyh v Lm elementiv
int m; //vidpovidae za nomer mnogyny (L(m))
int pathlen=0;
int path[kilver];
int vbegin =6;
int vend =7;
//-------------------------FUNCTION PROTOTYPES
void initialization(void);
void formuvannya_mnogyn(void);
int nalegnist(int j);
void zapys(int j, int m, int k);
void shortway(void);
void vyvid(void);
//--------------------------MAIN
void main(void)
{
clrscr();
initialization();
formuvannya_mnogyn();
shortway();
vyvid();
getch();
}
//-------------------------FUNCTIONS
void initialization(void)
{
for (int i=0; i<kilver ;i++)
{for (int j=0; j<q; j++){mnogyna[i][j]=-1;};nevybrani[i]=-1;}
}
//--------------------
void formuvannya_mnogyn(void)
{
int p; //budem vybyraty vershynu z L(m-1)
int j; //berem reshtu vershyn
mnogyna[0][0]=vbegin;
for(int i=0;i<kilver;i++){if(i==vbegin) nevybrani[i]=i;}
m=1;
do
{
k=0;
for(int i=0; mnogyna[m-1][i]>=0;i++) //vybyraem elementy z poperednyoi
// mnogyny
{
p=mnogyna[m-1][i]; //vybyraem Xp z L(m-1)
for(j=0; j<kilver;j++) //vybyraem Xj - dovilnu vershynu
{
if(matrycya_sumignosti[j][p]==1)//yaksho Xj sumigna z Xp
{
if(nalegnist(j)==0){zapys(j,m,k);k++;};
//yaksho Xj ne nalegyt do Lk, k<=m-1 todi
//formuem mnogynu Lm(zapys Xj)
}
}
}
m++;
}
...
